package sort;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * @Author: Hugh
 * @Date: 2021/4/10
 */
public class QuickSort2 {

    public static void quickSort(int[] target){
        if(target.length == 0){
            return;
        }
        int left = 0;
        int right = target.length -1;
        quickSort(target, left, right);
    }

    private static void  quickSort(int[] target, int left, int right) {
        if (left >= right) {
            return;
        }
        int i,j;
        i = left;
        j = right;
        //定义一个中枢值pivot，让其等于数组的左值，枢轴选定后永远不变，最终在中间，前小后大
        int currentVal = target[i];
        while (i < j)
        {
            while (i < j && target[j] > currentVal) {
                j--; // 从右向左找第一个小于x的数
            }

            if (i < j) {
                target[i++] = target[j];
            }
            while (i < j && target[i] < currentVal) {
                i++; // 从左向右找第一个大于x的数
            }
            if (i < j) {
                target[j--] = target[i];
            }
        }
        target[i] = currentVal;
        quickSort(target, left, j-1); /* 递归调用 */
        quickSort(target, j+1, right); /* 递归调用 */
    }

    // leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] arr = {9,8,867,34,345,745,568,8};
        quickSort(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            System.out.print(arr[i] + "  ");
        }
        System.out.print("\n");
        int[] arr1 = {3,2,1,5,6,4};
        quickSort(arr1);
        for (int i = arr1.length - 1; i >= 0; i--) {
            System.out.print(arr1[i] + "  ");
        }
        System.out.print("\n");
        int[] arr2 = {3,2,3,1,2,4,5,5,6};
        quickSort(arr2);
        for (int i = arr2.length - 1; i >= 0; i--) {
            System.out.print(arr2[i] + "  ");
        }
        System.out.println("---");
        int i=1;
        System.out.println( arr[i]);
        System.out.println( arr[i++]);
        System.out.println( i);
    }
}
